package solution;

import java.util.Deque;
import java.util.LinkedList;

/*
* 42
* */
public class Trap {

    /*
    * 使用暴力法
    * */
    public int solution1(int[] height) {
//        int ans = 0;
//        int size = height.length;
//        for (int i = 1 ; i < size - 1 ; i++){
//            int max_left = 0;
//            int max_right = 0;
//            for (int j = i ; j >= 0 ; j--){
//                max_left = Math.max(max_left, height[j]);
//            }
//            for (int j = i ; j < size ; j++){
//                max_right = Math.max(max_right, height[j]);
//            }
//            ans += Math.min(max_left, max_right) - height[i];
//        }
//        return ans;


        //优化写法
        int area = 0;
        if (height != null && height.length > 2){
            for (int i = 1 ; i < height.length - 1 ; i++){//坐标系左右不算边界
                int max_left = 0;
                int max_right = 0;
                for (int j = i ; j >= 0 ; j--){
                    max_left = Math.max(max_left, height[j]);
                }

                for (int j = i ; j < height.length ; j++){
                    max_right = Math.max(max_right, height[j]);
                }

                area += Math.min(max_left, max_right) - height[i];
            }
        }
        return area;
    }

    /*
    * 使用动态编程
    * */


    /*
    * 使用栈
    * */
    public int solution3(int[] height) {
        int ans = 0, current = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        while (current < height.length) {
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty())
                    break;
                int distance = current - stack.peek() - 1;
                int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
                ans += distance * bounded_height;
            }
            stack.push(current++);
        }
        return ans;
    }

}
